package com.mc.string;

import java.util.LinkedList;

public class Seriliz {
	public String Serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        
        LinkedList<TreeNode> que = new LinkedList<TreeNode>();
        if(root==null)
            return "";
        que.offer(root);
        while(!que.isEmpty()){
            TreeNode node = que.poll();
            if(node!=null){
                sb.append(String.valueOf(node.val));
                que.offer(node.left);
                que.offer(node.right);
            }
            else{
                sb.append("#");
            }
            sb.append(" ");
        }
        
        while(sb.charAt(sb.length()-1)=='#'||sb.charAt(sb.length()-1)==' ')
            sb.deleteCharAt(sb.length()-1);
        return sb.toString();
  }
    
	public TreeNode Deserialize(String str) {
       if(str==null||str.length()==0)
           return null;
        
        String[] ch = str.split(" ");
        TreeNode root = new TreeNode(Integer.parseInt(ch[0]));
        LinkedList<TreeNode> que = new LinkedList<TreeNode>();
        que.add(root);
        int i=1;
        while(i<ch.length){
            TreeNode curr = que.poll();
            if(!ch[i].equals("#")){
               	curr.left = new TreeNode(Integer.parseInt(ch[i])); 
            	que.add(curr.left);
                
            }
            if(i+1<ch.length&&!ch[i+1].equals("#")){
                curr.right = new TreeNode(Integer.parseInt(ch[i+1])); 
            	que.add(curr.right);
            }
            i+=2;
        }
        return root;
  }
	static class TreeNode{
		int val;
		TreeNode right;
		TreeNode left;
		TreeNode (int val){
			this.val = val;
			
		}
	}
}
